Technical Field
The present invention relates to information processing, and more particularly to real-time abnormal change detection in dynamic graphs.
Description of the Related Art
Information in several domains is often best represented in the form of graphs. Exemplary domains include, for example, social networks, transportation networks, biological networks, enterprise networks, and so forth. The entities in these networks form the vertices and the connections or interactions between the entities form the edges. For example, in a social network, people form the vertices, and their relationship and/or interactions form the edges. In an enterprise network, hosts form the vertices, and the network communications form the edges. Given that the data is modelled in this form, events happening in the real world continuously change the underlying graph structure. It is observed that different events change the graph in certain ways and there are certain peculiar events which change the structure of the underlying graph in very different ways.
Consider the spread of virus in the internet. The virus in a given host node in the network selects random Internet Protocol (IP) addresses in the network and infects those nodes in the network. The infection of a node by an already infected host is characterized by the addition of a directed edge from the infected host to the new node. Each infected node, in turn, replicates the same process. Virus spread usually occurs very fast. Therefore, a virus spread is characterized by the addition of a large number of edges in very small amount of time. These edges are not just randomly added but each node connects to a large number of hosts which increases the degree of the infecting host and this process is repeated for other nodes.
Another example is the spread of news on online social network sites like Twitter®. Here, the news spread starts by a particular user tweeting about an event and mentioning other users and adding some hashtags related to the event. This tweet is then received by his followers and users who have been mentioned in the tweet. These users in turn either retweet or post new tweets with the same hashtags and mention other users and the process continues. These kinds of spreads are quite common, however the degrees to which they propagate are different for different types of events. For example, some news about a natural calamity like a high magnitude earthquake affecting millions of people spreads very quickly among a large group of users over the entire network, while information about a local school being closed would spread only among a certain group of people within that locality.
Capturing these kinds of changes in the network in an online fashion as they are happening can be very useful and critical in some cases. However, a main drawback of the prior art is the lack of methods to detect abnormal changes in large and dynamic graphs in real-time. Thus, there is a need for real-time abnormal change detection in dynamic graphs.